{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-Concatenation Maximum Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kConcatenationMaxSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 次串联后最大子数组之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>arr</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，通过重复&nbsp;<code>k</code>&nbsp;次来修改数组。</p>\n",
    "\n",
    "<p>例如，如果&nbsp;<code>arr = [1, 2]</code>&nbsp;，<meta charset=\"UTF-8\" />&nbsp;<code>k = 3</code>&nbsp;，那么修改后的数组将是 <code>[1, 2, 1, 2, 1, 2]</code> 。</p>\n",
    "\n",
    "<p>返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 <code>0</code>，在这种情况下它的总和也是 <code>0</code>。</p>\n",
    "\n",
    "<p>由于&nbsp;<strong>结果可能会很大</strong>，需要返回的<meta charset=\"UTF-8\" />&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;的&nbsp;<strong>模</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2], k = 3\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,-2,1], k = 5\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [-1,-2], k = 7\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-concatenation-maximum-sum](https://leetcode.cn/problems/k-concatenation-maximum-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-concatenation-maximum-sum](https://leetcode.cn/problems/k-concatenation-maximum-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n3', '[1,-2,1]\\n5', '[-1,-2]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(arr)\n",
    "        dp = [float('-inf')]*n\n",
    "        dp = arr[0]\n",
    "        subdp = float('-inf')\n",
    "        left = 0\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            pre += arr[i]\n",
    "            left = max(left,pre)\n",
    "            if(i > 0):\n",
    "                dp = max(arr[i],dp+arr[i])\n",
    "            subdp = max(subdp, dp)\n",
    "        tsum = pre \n",
    "        right = 0\n",
    "        pre = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pre += arr[i]\n",
    "            right = max(right,pre)\n",
    "\n",
    "        print(left,right,subdp,tsum)\n",
    "\n",
    "        if(k == 1):\n",
    "            return max(subdp, 0) % M\n",
    "        if(k == 2):\n",
    "            return max(right+left, subdp,0) % M\n",
    "        return max(right + tsum*(k-2) + left, subdp, right+left, 0) % M\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        restList = []\n",
    "        rest = 0\n",
    "        curSum = 0\n",
    "        for i in range(3):\n",
    "            for num in arr:\n",
    "                curSum = max(curSum + num, num)\n",
    "                rest = max(curSum, rest)\n",
    "            rest %= mod\n",
    "            restList.append(rest)\n",
    "        if k == 1:\n",
    "            return restList[0]\n",
    "        maxSum2 = restList[1]\n",
    "        maxSum3 = restList[2]\n",
    "        x = maxSum3 - maxSum2\n",
    "        return ((k - 2) * x + maxSum2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        inner_max, l_max, r_max, tot = 0, 0, 0, 0\n",
    "        f = 0\n",
    "        for i in range(len(arr)):\n",
    "            tot += arr[i]\n",
    "            l_max = max(l_max, tot)\n",
    "            f = max(f, 0) + arr[i]\n",
    "            inner_max = max(f, inner_max)\n",
    "            if i==len(arr)-1:\n",
    "                r_max = f\n",
    "        \n",
    "        print(inner_max, l_max, r_max, tot)\n",
    "        if k==1:\n",
    "            return inner_max%(10**9+7)\n",
    "        else:\n",
    "            return max(inner_max, tot*k, l_max+r_max, l_max+r_max+tot*(k-2))%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        arrSum = 0\n",
    "        for num in arr:\n",
    "            arrSum += num\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        def getMaxSum(m):\n",
    "            rest = 0\n",
    "            curSum = 0\n",
    "            for i in range(m):\n",
    "                for num in arr:\n",
    "                    curSum = max(curSum + num, num)\n",
    "                    rest = max(curSum, rest)\n",
    "            return rest % mod\n",
    "\n",
    "        maxSum1 = getMaxSum(1)\n",
    "        if k == 1:\n",
    "            return maxSum1\n",
    "        maxSum2 = getMaxSum(2)\n",
    "        maxSum3 = getMaxSum(3)\n",
    "        maxSum4 = getMaxSum(4)\n",
    "        if maxSum2 == maxSum3:\n",
    "            return maxSum2\n",
    "        x = maxSum3 - maxSum2\n",
    "        return ((k - 2) * x + maxSum2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        if not arr: return 0\n",
    "        max_sub = arr[0] if arr[0] > 0 else 0\n",
    "        max_cur = max_sub\n",
    "        sum = arr[0]\n",
    "        n = len(arr)\n",
    "        i = 1\n",
    "        while i < min(k, 2) * n:\n",
    "            var = arr[i%n]\n",
    "            max_sub = max_sub + var if max_sub > 0 else var\n",
    "            max_cur = max(max_sub, max_cur)\n",
    "            if i < n:\n",
    "                sum += var\n",
    "            i += 1\n",
    "            print(i, max_sub, max_cur, sum)\n",
    "\n",
    "        max_cur = max_cur % 1000000007\n",
    "\n",
    "        if sum > 0:\n",
    "            max_cur += sum * max(k-2, 0) % 1000000007\n",
    "        return max_cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        # MOD = 10**9+7\n",
    "        # sums = 0\n",
    "        # total_sum = sum(arr)\n",
    "        # maxV = 0\n",
    "        # for x in arr:\n",
    "        #     sums = (max(0, sums) + x + MOD) % MOD\n",
    "        #     maxV = max(maxV, sums)\n",
    "        # if k == 1:\n",
    "        #     return maxV\n",
    "        # preSum, postSum = 0, 0\n",
    "        # maxPre, maxPost = 0, 0\n",
    "        # for i in range(len(arr)):\n",
    "        #     preSum = (preSum + arr[i] + MOD) % MOD\n",
    "        #     postSum = (postSum + arr[len(arr)-i-1] + MOD) % MOD\n",
    "        #     maxPre = max(maxPre, preSum)\n",
    "        #     maxPost = max(maxPost, postSum)\n",
    "        # maxV2 = maxPre + maxPost\n",
    "        # if total_sum > 0:\n",
    "        #     maxV2 = (maxV2 + total_sum*(k-2)) % MOD\n",
    "        # return max(maxV, maxV2)\n",
    "\n",
    "        # s, maxs = 0, 0\n",
    "        # for a in arr * min(2, k):\n",
    "        #     s = a if s < 0 else s + a   #连续和\n",
    "        #     if s > maxs: \n",
    "        #         maxs = s                #最大连续和\n",
    "        # if k <= 2: \n",
    "        #     return maxs                 #两个周期以内之间返回最大连续和\n",
    "        # return (max(sum(arr), 0) * (k - 2) + maxs) % 1000000007\n",
    "        #                                 #否则返回可能加上的多周期和\n",
    "\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        _MOD = 10 ** 9 + 7\n",
    "        v1 = -10001\n",
    "        t = -10001\n",
    "        for n in arr:\n",
    "            t = max(t + n, n)\n",
    "            v1 = max(v1, t)\n",
    "\n",
    "        if k == 1:\n",
    "            return v1 % _MOD if v1 > 0 else 0\n",
    "\n",
    "        v2 = v1\n",
    "        for n in arr:\n",
    "            t = max(t + n, n)\n",
    "            v2 = max(v2, t)\n",
    "\n",
    "        if k == 2:\n",
    "            return v2 % _MOD if v2 > 0 else 0\n",
    "\n",
    "        v3 = v2\n",
    "        for n in arr:\n",
    "            t = max(t + n, n)\n",
    "            v3 = max(v3, t)\n",
    "\n",
    "        if v2 == v3:\n",
    "            return v3 % _MOD if v3 > 0 else 0\n",
    "        else:\n",
    "            d = v3 - v2\n",
    "            return (v2 + (k - 2) * d) % _MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        n = len(nums)\n",
    "        s = -inf\n",
    "        l, r = 0, 0\n",
    "        total = 0\n",
    "        mid_max = 0\n",
    "        for i in range(n):\n",
    "            total += nums[i]\n",
    "            l = max(l, total)\n",
    "            s = max(s, 0) + nums[i]\n",
    "            mid_max = max(mid_max, s)\n",
    "            if i == n - 1:\n",
    "                r = s\n",
    "        if k == 1: return mid_max % MOD\n",
    "        if total >= 0:\n",
    "            return max(mid_max, l + r + total * (k - 2)) % MOD\n",
    "        return max(mid_max, l + r, 0) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # False\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        arr *= k\n",
    "        max_s, min_s = 0, 0\n",
    "        max_pre = min_pre = 0\n",
    "        for x in arr:\n",
    "            max_pre = max(max_pre, 0) + x\n",
    "            max_s = max(max_s, max_pre)\n",
    "            min_pre = min(min_pre, 0) + x\n",
    "            min_s = min(min_s, min_pre)\n",
    "        return max(sum(arr) - min_s, max_s) % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        tmp, mx = 0, 0\n",
    "        for _ in range(min(2, k)):\n",
    "            for x in arr:\n",
    "                tmp = max(tmp, 0) + x\n",
    "                mx = max(mx, tmp)\n",
    "        return (mx if k == 1 else mx + max(sum(arr) * (k - 2), 0)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(arr)\n",
    "        dp = [float('-inf')]*n\n",
    "        dp = arr[0]\n",
    "        subdp = float('-inf')\n",
    "        left = 0\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            pre += arr[i]\n",
    "            left = max(left,pre)\n",
    "            if(i > 0):\n",
    "                dp = max(arr[i],dp+arr[i])\n",
    "            subdp = max(subdp, dp)\n",
    "        tsum = pre \n",
    "        right = 0\n",
    "        pre = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pre += arr[i]\n",
    "            right = max(right,pre)\n",
    "\n",
    "        print(left,right,subdp,tsum)\n",
    "\n",
    "        if(k == 1):\n",
    "            return max(subdp, 0) % M\n",
    "        if(k == 2):\n",
    "            return max(right+left, subdp,0) % M\n",
    "        return max(right + tsum*(k-2) + left, subdp, right+left, 0) % M\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        pre = 0\n",
    "        dp1 , dp2 = 0 , 0\n",
    "        for i in range(0 , n):\n",
    "            if pre > 0:\n",
    "                pre = pre + arr[i]\n",
    "            else:\n",
    "                pre = arr[i]\n",
    "            dp1 = max(pre , dp1)\n",
    "        if k == 1:\n",
    "            return dp1\n",
    "        dp2 = dp1\n",
    "        for i in range(0 , n):\n",
    "            if pre > 0:\n",
    "                pre = pre + arr[i]\n",
    "            else:\n",
    "                pre = arr[i]\n",
    "            dp2 = max(pre , dp2)\n",
    "        pre = dp2\n",
    "        if k > 2:\n",
    "            pre += (k - 2) * s\n",
    "        return max(dp1 , max(dp2 , pre)) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        dp = 0\n",
    "        ans = 0\n",
    "        arrSum = 0\n",
    "        prefixSumMax = float('-inf')\n",
    "        for num in arr:\n",
    "            if dp > 0:\n",
    "                dp += num\n",
    "            else:\n",
    "                dp = num\n",
    "            ans = max(ans, dp)\n",
    "            arrSum += num\n",
    "            prefixSumMax = max(prefixSumMax, arrSum)\n",
    "        if k == 1:\n",
    "            return ans\n",
    "        ans = max(ans, dp + max((k - 2) * arrSum, 0) + max(prefixSumMax, 0))\n",
    "        ans %= (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        total = sum(arr)\n",
    "        ans = prev = 0\n",
    "        for x in range(min(k,2)):\n",
    "            for i in range(0, n):\n",
    "                cur = max(prev + arr[i], arr[i])\n",
    "                ans = max(ans, cur)\n",
    "                prev = cur\n",
    "        if k > 2 and total > 0:\n",
    "            ans += (k-2) * total\n",
    "\n",
    "        return ans % MOD\n",
    "    def kConcatenationMaxSum1(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        MOD = 10 ** 9 + 7\n",
    "    \n",
    "        for x in range(k):\n",
    "            for i in range(0, n):\n",
    "                cur = max(prev + arr[i], arr[i])\n",
    "                ans = max(ans, cur)\n",
    "                prev = cur\n",
    "        # 时间复杂度O(k*n) 超时\n",
    "        return ans % MOD\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        # MOD = 10**9+7\n",
    "        # sums = 0\n",
    "        # total_sum = sum(arr)\n",
    "        # maxV = 0\n",
    "        # for x in arr:\n",
    "        #     sums = (max(0, sums) + x + MOD) % MOD\n",
    "        #     maxV = max(maxV, sums)\n",
    "        # if k == 1:\n",
    "        #     return maxV\n",
    "        # preSum, postSum = 0, 0\n",
    "        # maxPre, maxPost = 0, 0\n",
    "        # for i in range(len(arr)):\n",
    "        #     preSum = (preSum + arr[i] + MOD) % MOD\n",
    "        #     postSum = (postSum + arr[len(arr)-i-1] + MOD) % MOD\n",
    "        #     maxPre = max(maxPre, preSum)\n",
    "        #     maxPost = max(maxPost, postSum)\n",
    "        # maxV2 = maxPre + maxPost\n",
    "        # if total_sum > 0:\n",
    "        #     maxV2 = (maxV2 + total_sum*(k-2)) % MOD\n",
    "        # return max(maxV, maxV2)\n",
    "\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            total += x\n",
    "            total = max(total, 0)\n",
    "            ans = max(ans, total)\n",
    "        if k == 1:\n",
    "            return ans\n",
    "        total = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            total += x\n",
    "            l = max(l, total)\n",
    "        total = 0\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            total += arr[i]\n",
    "            r = max(r, total)\n",
    "        \n",
    "        if total > 0:\n",
    "            ans = max((total * (k - 2) + l + r), ans)\n",
    "        else:\n",
    "            ans = max(l + r, ans)\n",
    "        \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        maxv = 0\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        for i in range(n * min(2, k)):\n",
    "            j = i % n\n",
    "            maxv = max(maxv + arr[j], arr[j])\n",
    "            ans = max(ans, maxv)\n",
    "        sums = sum(arr)\n",
    "        if sums > 0 and k > 2:\n",
    "            return (ans + sums * (k - 2)) % (10 ** 9 + 7)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:        \n",
    "        prev = arr[0]\n",
    "        max_single_sum = max(0, prev)\n",
    "        for ii in range(1, len(arr)):\n",
    "            prev = max(arr[ii], prev + arr[ii])\n",
    "            max_single_sum = max(max_single_sum, prev)\n",
    "        \n",
    "        if k == 1:\n",
    "            return max_single_sum\n",
    "        \n",
    "        first_chunk_sum = 0\n",
    "        current_sum = 0\n",
    "\n",
    "        for ii in reversed(arr):\n",
    "            current_sum += ii\n",
    "            first_chunk_sum = max(first_chunk_sum, current_sum)\n",
    "        \n",
    "        current_sum = 0\n",
    "        last_chunk_max = 0\n",
    "        for ii in arr:\n",
    "            current_sum += ii\n",
    "            last_chunk_max = max(last_chunk_max, current_sum)\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        arr_sum = sum(arr)\n",
    "        # print(first_chunk_sum, last_chunk_max, arr_sum)\n",
    "        return max(0, first_chunk_sum + max(0, max(0, k - 2) * arr_sum) + last_chunk_max, max_single_sum) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        pre_sum = 0\n",
    "        min_pre = 0\n",
    "        ans = 0\n",
    "        k1 = min(k,2)\n",
    "        for i in range(n*k1):\n",
    "            pre_sum += arr[i%n]\n",
    "            ans = max(ans,pre_sum-min_pre)\n",
    "            min_pre = min(min_pre,pre_sum)\n",
    "        if k <= 2: \n",
    "            return ans % 1000000007                #两个周期以内之间返回最大连续和\n",
    "        return (max(sum(arr), 0) * (k - 2) + ans) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        s = sum(arr)\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        \n",
    "        # s = 0\n",
    "        # for x in arr:\n",
    "        #     print(x)\n",
    "        #     s += x\n",
    "        #     print(s)\n",
    "        #     s %= MOD\n",
    "        #     print(s)\n",
    "\n",
    "        max_s, min_s = -inf, inf\n",
    "        max_f = min_f = 0\n",
    "\n",
    "\n",
    "        for num in arr:\n",
    "            max_f = max(max_f , 0) + num\n",
    "            # max_f = max_f % MOD if max_f >= 0 else max_f % MOD - MOD\n",
    "            max_s = max(max_s, max_f)\n",
    "\n",
    "            min_f = min(min_f, 0) + num\n",
    "            # min_f = min_f % MOD if min_f >= 0 else min_f % MOD - MOD\n",
    "            min_s = min(min_s, min_f)\n",
    "        \n",
    "        # print(min_s, max_s)\n",
    "        # print(s)\n",
    "\n",
    "        def multiply(x, y):\n",
    "            res = 0\n",
    "            for k in range(y):\n",
    "                res += x\n",
    "                res %= MOD\n",
    "            return res\n",
    "\n",
    "        if s >= 0:\n",
    "            # \n",
    "            c1 = max_s + multiply(s, k-1) #  (s * (k-1)) % MOD\n",
    "            c2 = s - min_s + multiply(s, k-2) # (s * (k-2)) % MOD\n",
    "            c1 %= MOD\n",
    "            c2 %= MOD\n",
    "            if k > 1:\n",
    "                return max(c1, c2)\n",
    "            else:\n",
    "                return c1\n",
    "\n",
    "        else:\n",
    "            # s < 0\n",
    "            if k > 1:\n",
    "                return max(max_s, s - min_s)\n",
    "            else:\n",
    "                return max(max_s, 0) # max(max_s, s - min_s)\n",
    "\n",
    "        # if k == 1:\n",
    "        #     # 如果nums都是负数/sum为负数\n",
    "        #     if min_s == s:\n",
    "        #         return max_s\n",
    "        #     return max(max_s, s - min_s)\n",
    "        \n",
    "\n",
    "        # if k >= 2:\n",
    "        #     res2 = (k-2)*s + s - min_s\n",
    "        #     return max(res2, max_s, s - min_s)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        pre_sum = 0\n",
    "        min_pre = 0\n",
    "        ans = 0\n",
    "        k1 = min(k,2)\n",
    "        for i in range(n*k1):\n",
    "            pre_sum += arr[i%n]\n",
    "            ans = max(ans,pre_sum-min_pre)\n",
    "            min_pre = min(min_pre,pre_sum)\n",
    "        if k <= 2: \n",
    "            return ans % 1000000007                #两个周期以内之间返回最大连续和\n",
    "        return (max(sum(arr), 0) * (k - 2) + ans) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        pre = 0\n",
    "        dp1 , dp2 = 0 , 0\n",
    "        for i in range(0 , n):\n",
    "            if pre > 0:\n",
    "                pre = pre + arr[i]\n",
    "            else:\n",
    "                pre = arr[i]\n",
    "            dp1 = max(pre , dp1)\n",
    "        if k == 1:\n",
    "            return dp1\n",
    "        dp2 = dp1\n",
    "        for i in range(0 , n):\n",
    "            if pre > 0:\n",
    "                pre = pre + arr[i]\n",
    "            else:\n",
    "                pre = arr[i]\n",
    "            dp2 = max(pre , dp2)\n",
    "        pre = dp2\n",
    "        if k > 2:\n",
    "            pre += (k - 2) * s\n",
    "        return max(dp2 , pre) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        M = 10**9+7\n",
    "        n = len(arr)\n",
    "        dp = [float('-inf')]*n\n",
    "        dp = arr[0]\n",
    "        subdp = float('-inf')\n",
    "        left = 0\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            pre += arr[i]\n",
    "            left = max(left,pre)\n",
    "            if(i > 0):\n",
    "                dp = max(arr[i],dp+arr[i])\n",
    "            subdp = max(subdp, dp)\n",
    "        tsum = pre \n",
    "        right = 0\n",
    "        pre = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pre += arr[i]\n",
    "            right = max(right,pre)\n",
    "        if(k == 1):\n",
    "            return max(subdp, 0) % M\n",
    "        if(k == 2):\n",
    "            return max(right+left, subdp,0) % M\n",
    "        return max(right + tsum*(k-2) + left, subdp, right+left, 0) % M\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        def f(nums):\n",
    "            ans = 0\n",
    "            tmp = 0\n",
    "            for num in nums:\n",
    "                tmp += num\n",
    "                ans = max(ans, tmp)\n",
    "                tmp = max(0, tmp)\n",
    "            return ans\n",
    "        if k==1:\n",
    "            return f(arr)\n",
    "        return (max(0, (k-2)*sum(arr))+f(arr*2))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=max(sum(arr),0)\n",
    "        return (findmaxsum(arr*2)+sum0*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        # MOD = 10**9+7\n",
    "        # sums = 0\n",
    "        # total_sum = sum(arr)\n",
    "        # maxV = 0\n",
    "        # for x in arr:\n",
    "        #     sums = (max(0, sums) + x + MOD) % MOD\n",
    "        #     maxV = max(maxV, sums)\n",
    "        # if k == 1:\n",
    "        #     return maxV\n",
    "        # preSum, postSum = 0, 0\n",
    "        # maxPre, maxPost = 0, 0\n",
    "        # for i in range(len(arr)):\n",
    "        #     preSum = (preSum + arr[i] + MOD) % MOD\n",
    "        #     postSum = (postSum + arr[len(arr)-i-1] + MOD) % MOD\n",
    "        #     maxPre = max(maxPre, preSum)\n",
    "        #     maxPost = max(maxPost, postSum)\n",
    "        # maxV2 = maxPre + maxPost\n",
    "        # if total_sum > 0:\n",
    "        #     maxV2 = (maxV2 + total_sum*(k-2)) % MOD\n",
    "        # return max(maxV, maxV2)\n",
    "\n",
    "        s, maxs = 0, 0\n",
    "        for a in arr * min(2, k):\n",
    "            s = a if s < 0 else s + a   #连续和\n",
    "            if s > maxs: \n",
    "                maxs = s                #最大连续和\n",
    "        if k <= 2: \n",
    "            return maxs % 1000000007                #两个周期以内之间返回最大连续和\n",
    "        return (max(sum(arr), 0) * (k - 2) + maxs) % 1000000007\n",
    "\n",
    "        acc, m = 0, 0\n",
    "        for _ in range(min(k, 2)):\n",
    "            for n in arr:\n",
    "                acc= max(0, acc)+n\n",
    "                m = max(m, acc)\n",
    "        return (m if k==1 else m+ max(sum(arr) *(k - 2) , 0)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def solve(arr):\n",
    "            dp  = res  = 0\n",
    "            for x in arr:\n",
    "                dp = max(dp + x, x)\n",
    "                res = max(res, dp)\n",
    "            return res \n",
    "        if sum(arr) <= 0:\n",
    "            res = solve(arr * 2) if k > 1 else solve(arr)\n",
    "            return res % mod\n",
    "        else:\n",
    "            min_pre = min_suf = 0\n",
    "            ss = 0\n",
    "            for i in range(len(arr)):\n",
    "                ss += arr[i]\n",
    "                min_pre = min(min_pre, ss)\n",
    "            ss = 0\n",
    "            for i in range(len(arr) - 1, -1 , -1):\n",
    "                ss += arr[i]\n",
    "                min_suf = min(min_suf, ss)\n",
    "            return (sum(arr) * k - min_pre - min_suf) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        sum0=sum(arr)\n",
    "        sum1=0\n",
    "        if sum0>0:\n",
    "            sum1=sum0\n",
    "        sum0=findmaxsum(arr*2)\n",
    "        return (sum0+sum1*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        sum0=sum(arr)\n",
    "        sum1=0\n",
    "        if sum0>0:\n",
    "            sum1=sum0\n",
    "        sum0=findmaxsum(arr*2)\n",
    "        return (sum0+sum1*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=sum(arr)\n",
    "        sum1=0\n",
    "        if sum0>0:\n",
    "            sum1=sum0\n",
    "        sum0=findmaxsum(arr*2)\n",
    "        return (sum0+sum1*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=max(sum(arr),0)\n",
    "        return (findmaxsum(arr*2)+sum0*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=max(sum(arr),0)\n",
    "        return (findmaxsum(arr*2)+sum0*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        count = 0\n",
    "        result = 0\n",
    "        for a in arr*min(2,k):\n",
    "            count += a\n",
    "            if count > result:\n",
    "                result = count\n",
    "            if count <= 0:count = 0\n",
    "        \n",
    "        if k <= 2:\n",
    "            return result%mod\n",
    "        return (max(sum(arr),0)*(k-2)+result)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        a = arr * min(k, 2)\n",
    "        ans = pre = 0\n",
    "        for i in range(len(a)):\n",
    "            pre = max(a[i], pre + a[i])\n",
    "            ans = max(ans, pre)\n",
    "        s = sum(arr)\n",
    "        if s > 0 and k > 2:\n",
    "            ans = max(ans, s * (k - 2) + ans)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=sum(arr)\n",
    "        sum1=0\n",
    "        if sum0>0:\n",
    "            sum1=sum0\n",
    "        sum0=findmaxsum(arr*2)\n",
    "        return (sum0+sum1*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        s, maxs = 0, 0\n",
    "        for a in arr * min(2, k):\n",
    "            s = a if s < 0 else s + a   #连续和\n",
    "            if s > maxs: \n",
    "                maxs = s                #最大连续和\n",
    "        if k <= 2: \n",
    "            return maxs % 1000000007               #两个周期以内之间返回最大连续和\n",
    "        return (max(sum(arr), 0) * (k - 2) + maxs) % 1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        # 分三种情况\n",
    "        # k = 1: 同 53 题 注意 答案非负数\n",
    "        # k = 2: 最大前缀和 + 最大后缀和， 其实两个合起来同(1)\n",
    "        # k > 2: sum < 0, 同(2)；否则(2)答案 + sum * (k - 2)\n",
    "        a = arr * min(k, 2)\n",
    "        ans = 0\n",
    "        pre = 0 \n",
    "\n",
    "        for i, x in enumerate(a):\n",
    "            pre = max(x, pre + x)\n",
    "            ans = max(ans, pre)\n",
    "        s = sum(arr)\n",
    "        if s > 0 and k > 2:\n",
    "            ans = max(ans, s * (k-2) + ans)\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def f(arr: List[int]) -> int:\n",
    "            r = 0\n",
    "            cur = 0\n",
    "            for a in arr:\n",
    "                cur = max(cur+a, a)\n",
    "                r = max(r, cur)\n",
    "            return r\n",
    "        result = 0\n",
    "        s1 = f(arr)\n",
    "        if k == 1:\n",
    "            result = max(s1, result)\n",
    "        else:\n",
    "            s = sum(arr)\n",
    "            s2 = f(arr+arr)\n",
    "            if s > 0:\n",
    "                result = max(s*(k-2)+s2, result)\n",
    "            else:\n",
    "                result = max(s2, result)\n",
    "        return result%1000000007\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def findmaxsum(arr):\n",
    "            min_sum=0\n",
    "            res=0\n",
    "            sum0=0\n",
    "            for num in arr:\n",
    "                sum0+=num\n",
    "                if sum0-min_sum>res:\n",
    "                    res=sum0-min_sum\n",
    "                if sum0<min_sum:\n",
    "                    min_sum=sum0\n",
    "            return res\n",
    "\n",
    "        if k==1:\n",
    "            return findmaxsum(arr)\n",
    "        elif k==2:\n",
    "            return findmaxsum(arr*2)%(10**9+7)\n",
    "        sum0=sum(arr)\n",
    "        sum1=0\n",
    "        if sum0>0:\n",
    "            sum1=sum0\n",
    "        sum0=findmaxsum(arr*2)\n",
    "        return (sum0+sum1*(k-2))%(10**9+7)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        s, maxs = 0, 0\n",
    "        for a in arr * min(2, k):\n",
    "            s = a if s < 0 else s + a   #连续和\n",
    "            if s > maxs: \n",
    "                maxs = s                #最大连续和\n",
    "        if k <= 2: \n",
    "            return maxs   % 1000000007               #两个周期以内之间返回最大连续和\n",
    "        return (max(sum(arr), 0) * (k - 2) + maxs) % 1000000007\n",
    "                                        #否则返回可能加上的多周期和\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMax(self,arr):\n",
    "        '''\n",
    "        计算最大子数组和\n",
    "        '''\n",
    "        ans = 0\n",
    "        min_pre = 0\n",
    "        tmp = 0\n",
    "        for i in arr:\n",
    "            tmp +=i\n",
    "            min_pre = min(min_pre,tmp)\n",
    "            ans = max(ans,tmp-min_pre)\n",
    "        return ans\n",
    "    \n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        # 三种情况\n",
    "        ans = [0]\n",
    "        # sum_*k\n",
    "        \n",
    "        sum_ = sum(arr)\n",
    "        if sum_*k>0:\n",
    "            ans.append(sum_*k)\n",
    "        \n",
    "        # max_pre # 最大前缀和\n",
    "        max_pre= self.getMax(arr) # 最大前缀和\n",
    "        if max_pre>0:\n",
    "         ans.append(max_pre)\n",
    "\n",
    "        # max_pre+max_suf\n",
    "        arr.extend(arr)\n",
    "        if k>1:\n",
    "            max_pre_suf = self.getMax(arr)\n",
    "            if max_pre_suf>0:\n",
    "                ans.append(max_pre_suf)\n",
    "\n",
    "        # sum_*(k-2)+max_pre+max_suf\n",
    "        if k>2 and (sum_*(k-2)+max_pre_suf)>0:\n",
    "            ans.append(sum_*(k-2)+max_pre_suf)\n",
    "        \n",
    "        return max(ans)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        prefix = [0]*(len(arr)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + arr[i-1]\n",
    "        # 直接找一个prefix当中的最大差值就行了\n",
    "        res = 0\n",
    "        minnum = inf\n",
    "        for i in range(len(prefix)):\n",
    "            res = max(res,prefix[i]-minnum)\n",
    "            minnum = min(prefix[i],minnum)\n",
    "        maxnum = max(prefix)\n",
    "        minnum = min(prefix)\n",
    "        if prefix[-1] < 0:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            return max(maxnum+prefix[-1]-minnum,res)\n",
    "        else:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            maxnum = max(prefix) + prefix[-1]*(k-1)\n",
    "            minnum = min(prefix)\n",
    "            return (maxnum-minnum)%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        prefix = [0]*(len(arr)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + arr[i-1]\n",
    "        # 直接找一个prefix当中的最大差值就行了\n",
    "        res = 0\n",
    "        minnum = inf\n",
    "        maxnum = -inf \n",
    "        for i in range(len(prefix)):\n",
    "            res = max(res,prefix[i]-minnum)\n",
    "            minnum = min(prefix[i],minnum)\n",
    "            maxnum = max(prefix[i],maxnum)\n",
    "        if prefix[-1] < 0:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            return max(maxnum+prefix[-1]-minnum,res)\n",
    "        else:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            maxnum = max(prefix) + prefix[-1]*(k-1)\n",
    "            minnum = min(prefix)\n",
    "            return (maxnum-minnum)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        prefix = [0]*(len(arr)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + arr[i-1]\n",
    "        # 直接找一个prefix当中的最大差值就行了\n",
    "        res = 0\n",
    "        minnum = inf\n",
    "        maxnum = -inf \n",
    "        for i in range(len(prefix)):\n",
    "            res = max(res,prefix[i]-minnum)\n",
    "            minnum = min(prefix[i],minnum)\n",
    "            maxnum = max(prefix[i],maxnum)\n",
    "        if prefix[-1] < 0:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            return max(maxnum+prefix[-1]-minnum,res)\n",
    "        else:\n",
    "            if k == 1:\n",
    "                return res\n",
    "            maxnum = max(prefix) + prefix[-1]*(k-1)\n",
    "            minnum = min(prefix)\n",
    "            return (maxnum-minnum)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        def func(arr):\n",
    "            total = 0\n",
    "            best = 0\n",
    "            for i in arr:\n",
    "                total = max(total,0) + i\n",
    "                best = max(total,best)\n",
    "            return best\n",
    "        if k == 1:\n",
    "            return func(arr) % mod\n",
    "        elif k == 2:\n",
    "            return func(arr * 2) % mod\n",
    "        s1 = func(arr) % mod\n",
    "        s2 = func(arr * 2) % mod\n",
    "        s3 = func(arr * 3) % mod\n",
    "\n",
    "        if s2 == s3:\n",
    "            return s2\n",
    "        elif s2 * 2 == s3 + s1:\n",
    "            return (s1 + (s2 - s1)* (k - 1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0] * (n + 1)\n",
    "        d = [0] * n\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + arr[i]\n",
    "            d[i] = max(d[i-1] + arr[i], 0)\n",
    "        if k == 1:\n",
    "            return max(d)\n",
    "        return max(max(d), max(s[n], 0) * (k - 2) + s[n] - min(s) + max(s))% (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        s, d = [0] * (n + 1), [0] * n\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + arr[i]        #前缀和\n",
    "            d[i] = max(d[i - 1] + arr[i], 0)#最大连续和\n",
    "        if k == 1:\n",
    "            return max(d) % 1000000007                  #如果只有一个周期，就直接输出最大的连续和\n",
    "        return max(max(d), max(s[n], 0) * (k - 2) + s[n] - min(s) + max(s)) % 1000000007\n",
    "                                            #比较一个周期的最大连续和以及多个周期的总和大小\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        ma = 0\n",
    "        cur = 0\n",
    "        for x in arr:\n",
    "            cur += x\n",
    "            ma = max(ma, cur)\n",
    "            if cur < 0:\n",
    "                cur = 0\n",
    "        n = len(arr)\n",
    "        pre = [0]\n",
    "        for x in arr:\n",
    "            pre.append(pre[-1] + x)\n",
    "        \n",
    "        post = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            post[i] = post[i + 1] + arr[i]\n",
    "        \n",
    "        MOD = 10**9 + 7\n",
    "        max_pre = max(pre)\n",
    "        max_post = max(post)\n",
    "        s = sum(arr)\n",
    "        if s <= 0:\n",
    "            if k == 1:\n",
    "                return max(max_post, max_pre, ma) % MOD\n",
    "            return max(ma, max_pre + max_post) % MOD\n",
    "        else:\n",
    "            return max(ma, max_pre + max_post + s * (k - 2)) % MOD\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        s, d = [0] * (n + 1), [0] * n\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + arr[i]\n",
    "            d[i] = max(0, d[i - 1] + arr[i])\n",
    "        if k == 1:\n",
    "            return max(d)\n",
    "        return max(max(d), max(s[n], 0) * (k - 2) + s[n] - min(s) + max(s)) % 1000000007   \n",
    "         \n",
    "    def kConcatenationMaxSum1(self, arr: List[int], k: int) -> int:\n",
    "        s = sum(arr)\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        \n",
    "        # s = 0\n",
    "        # for x in arr:\n",
    "        #     print(x)\n",
    "        #     s += x\n",
    "        #     print(s)\n",
    "        #     s %= MOD\n",
    "        #     print(s)\n",
    "\n",
    "        max_s, min_s = -inf, inf\n",
    "        max_f = min_f = 0\n",
    "\n",
    "\n",
    "        for num in arr:\n",
    "            max_f = max(max_f , 0) + num\n",
    "            # max_f = max_f % MOD if max_f >= 0 else max_f % MOD - MOD\n",
    "            max_s = max(max_s, max_f)\n",
    "\n",
    "            min_f = min(min_f, 0) + num\n",
    "            # min_f = min_f % MOD if min_f >= 0 else min_f % MOD - MOD\n",
    "            min_s = min(min_s, min_f)\n",
    "        \n",
    "        # print(min_s, max_s)\n",
    "        # print(s)\n",
    "\n",
    "        def multiply(x, y):\n",
    "            res = 0\n",
    "            for k in range(y):\n",
    "                res += x\n",
    "                res %= MOD\n",
    "            return res\n",
    "\n",
    "        if s >= 0:\n",
    "            # \n",
    "            c1 = max_s + multiply(s, k-1) #  (s * (k-1)) % MOD\n",
    "            c2 = s - min_s + multiply(s, k-2) # (s * (k-2)) % MOD\n",
    "            c1 %= MOD\n",
    "            c2 %= MOD\n",
    "            if k > 1:\n",
    "                return max(c1, c2)\n",
    "            else:\n",
    "                return c1\n",
    "\n",
    "        else:\n",
    "            # s < 0\n",
    "            if k > 1:\n",
    "                return max(max_s, s - min_s)\n",
    "            else:\n",
    "                return max(max_s, 0) # max(max_s, s - min_s)\n",
    "\n",
    "        # if k == 1:\n",
    "        #     # 如果nums都是负数/sum为负数\n",
    "        #     if min_s == s:\n",
    "        #         return max_s\n",
    "        #     return max(max_s, s - min_s)\n",
    "        \n",
    "\n",
    "        # if k >= 2:\n",
    "        #     res2 = (k-2)*s + s - min_s\n",
    "        #     return max(res2, max_s, s - min_s)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        pre = [0] * n\n",
    "        x = 0\n",
    "        for i in range(n):\n",
    "            x = x if x > 0 else 0\n",
    "            x += arr[i]\n",
    "            pre[i] = x\n",
    "\n",
    "        post = [0] * n\n",
    "        x = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = x if x > 0 else 0\n",
    "            x += arr[i]\n",
    "            post[i] = x\n",
    "        ans = max(0, max(pre))\n",
    "        if k > 1:\n",
    "            if pre[-1] + post[0] > ans:\n",
    "                ans = pre[-1] + post[0]\n",
    "            if pre[-1] + post[0] + s * (k - 2) > ans:\n",
    "                ans = pre[-1] + post[0] + s * (k - 2)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        def solve(arr,k):\n",
    "            if len(arr) == 0:\n",
    "                return 0\n",
    "            new_arr = []\n",
    "            for i in range(k):\n",
    "                new_arr += arr\n",
    "\n",
    "            res = 0\n",
    "            dp = [0] * len(new_arr)\n",
    "            for i in range(len(new_arr)):\n",
    "                if i == 0:\n",
    "                    dp[i] = new_arr[i]\n",
    "                else:\n",
    "                    dp[i] = max(new_arr[i],dp[i-1] + new_arr[i])\n",
    "                res = max(res,dp[i])\n",
    "            return res\n",
    "\n",
    "        if k < 3:\n",
    "            return solve(arr,k) % (10 ** 9 + 7)\n",
    "\n",
    "        k_1_sum = solve(arr,1)\n",
    "        k_2_sum = solve(arr,2)\n",
    "\n",
    "        res = max(k_1_sum,k_2_sum,(k-2)*sum(arr)+k_2_sum)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(arr)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+arr[i]\n",
    "        l,r,mid=max(pre),pre[-1],pre[-1]\n",
    "        for i in range(n):\n",
    "            r=max(pre[-1]-pre[i],r)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            if dp[i]>0:\n",
    "                dp[i+1]=dp[i]+arr[i]\n",
    "            else:\n",
    "                dp[i+1]=arr[i]\n",
    "        mid=max(dp)\n",
    "        if mid<=0:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return mid%mod\n",
    "        merge=max(l,r,l+r)\n",
    "        if pre[-1]<=0:\n",
    "            return max(merge,mid)%mod\n",
    "        return (pre[-1]*(k-2)+merge)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        s = sum(arr)\n",
    "        pre = [0]*(n+1)\n",
    "        x = 0\n",
    "        for i in range(n):\n",
    "            x= x if x > 0 else 0\n",
    "            x += arr[i]\n",
    "            if x > ans:\n",
    "                ans = x\n",
    "            pre[i+1] = x\n",
    "        \n",
    "        post = [0]*(n+1)\n",
    "        x = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = x if x > 0 else 0\n",
    "            x += arr[i]\n",
    "            if x > ans:\n",
    "                ans = x\n",
    "            post[i] = x\n",
    "        if k > 1:\n",
    "            if pre[-1] + post[0] > ans:\n",
    "                ans = pre[-1]+post[0]\n",
    "            if pre[-1]+post[0] + s*(k-2) > ans:\n",
    "                ans = pre[-1]+post[0] + s*(k-2)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        sumarr = sum(arr)\n",
    "        ret = max(0, sumarr*k)\n",
    "        # if k == 1: return ret\n",
    "        arr *= min(2, k)\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] += arr[i-1]\n",
    "        min_num = arr[0]\n",
    "        tmp = 0\n",
    "        for i in arr:\n",
    "            tmp = max(tmp, i, i-min_num)\n",
    "            min_num = min(i, min_num)\n",
    "        if k == 1: return tmp\n",
    "        ret = max(ret, tmp + sumarr * (k-2), tmp)\n",
    "        return ret % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            max_dp, max_idx = self.calculate_max_sum(arr)\n",
    "            return max(max_dp, 0)\n",
    "        # 先求 两个 arr 串联起来的\n",
    "        # 如果 sum(arr) > 0且最优是在第一个arr中, 那么计算 max_dp + (k - 1) * s\n",
    "        # 如果 sum(arr) > 0且最优是在第二个arr中, 那么中间再插入 k - 2个也是最优的\n",
    "        # 如果 sum(arr) < 0且最优是在第一个arr中, 那么最优就是 max_dp\n",
    "        # 如果 sum(arr) < 0且最优是在第二个arr中, 那么最优就是 max_dp\n",
    "        n = len(arr)\n",
    "        new_arr = [n for n in arr]\n",
    "        new_arr.extend([n for n in arr])\n",
    "        max_dp, max_idx = self.calculate_max_sum(new_arr)\n",
    "\n",
    "        # 根据上方规则\n",
    "        res = 0\n",
    "        t = sum(arr)\n",
    "        if t >= 0 and max_idx < n - 1:\n",
    "            res = (k - 1) * t + max_dp\n",
    "        elif t >= 0 and max_idx >= n - 1:\n",
    "            res = (k - 2) * t + max_dp\n",
    "        else:\n",
    "            res = max_dp\n",
    "        return max(res, 0) % (10 ** 9 + 7)\n",
    "    \n",
    "    def calculate_max_sum(self, arr):\n",
    "        n = len(arr)\n",
    "        dp = arr[:]\n",
    "        max_idx = 0\n",
    "        max_dp = arr[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i - 1] + arr[i], arr[i])\n",
    "            if dp[i] > max_dp:\n",
    "                max_dp = dp[i]\n",
    "                max_idx = i\n",
    "        return max_dp, max_idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n",
    "        s = sum(arr)\n",
    "\n",
    "        def getMax(arr, end = 1):\n",
    "            n = len(arr)\n",
    "            dp = [0] * n \n",
    "            dp[0] = max(arr[0], dp[0])\n",
    "            for i in range(n):\n",
    "                dp[i] = max(dp[i], dp[i - 1] + arr[i], arr[i], 0)\n",
    "            if end: return dp[-1]\n",
    "            return max(dp)\n",
    "\n",
    "        if k == 1: return getMax(arr, 0)\n",
    "        if s > 0: return ((getMax(arr + arr, 0)) + ((s * (k - 2)) % MOD)) % MOD\n",
    "        else: return (getMax(arr + arr, 0)) % MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
